COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Here is the revised scope information.  It is revised from the copy
C00017 ENDMK
C⊗;
Here is the revised scope information.  It is revised from the copy
mailed by Ohlander to Betty Scott.  The revisions were performed as
follows:
A. by McCarthy who stands by it.
B. by Luckham who stands by it.
C. by Manna who stands by it.
D. by McCarthy in the absence of Wiederhold.  Only trivial revisions were made.
E. by Binford who stands by it.
F. by McCarthy in the absence of Knuth.  It is abstracted from the main proposal.
G. by McCarthy in the absence of Golub.  It is abstracted from the main proposal.


Stanford University will perform Research as follows:


A. Basic Research in Artificial Intelligence
--------------------------------------------

1. Develop formalizations of facts about the common sense world including laws
determining the effects of actions including mental actions.

2. Develop formalizations (both procedural and declarative) of the
heuristic knowledge used in common sense reasoning and problem solving.

3. Develop formalization of common sense reasoning including non-monotonic
reasoning.

4. Study representation of facts in the memory of a computer including the
connections between AI representation work and database research.

5. Develop languages for communications among computers and between
computers and people, emphasizing the semantic aspects of such languages
relevant to commercial and military communications.

6. Develop systems for computer reasoning and computer-assisted human reasoning.

7. Improve AI Programming languages including LISP, especially Common
Lisp, and also perform research aimed at new languages.

8. Experiment with techniques of automatically specializing programs to
make them run faster when part of their data is constant.

9. Develop programs that take advice from users and give advice in return,
and programs that decide what to do by formal reasoning.


B. Research and Development for Advanced Programming Environments
-----------------------------------------------------------------

Stanford will investigate advanced techniques for production and maintenance
of software.  This research has the goal of developing automated aids for all
stages of the production of software systems (requirements, design,
implementation, and maintenance). New high level languages will be designed.
Tools providing automated support for these languages will be developed and
techniques for integrating them into programming environments will be studied.
Special emphasis is placed on the production of new complex systems that
utilize concurrent and distributed processing.  The research will focus
primarily on software, but applicability to hardware design will also be
studied.

Specific projects will be undertaken within each of the following tasks:

1. Design new high level languages for formulation of systems requirements,
design specifications, formal annotation of implementations, and
documentation.  Such languages are to be machine processable.

2. Develop techniques and guidelines for specifying systems designs and
implementations in these languages.

3. Design, implement, and test tools supporting software production in these
languages. Such support tools will include tools for (i) testing and
validation of requirements, design specifications, and implementations, (ii)
compilation of specifications for rapid prototyping, and (iii) formal
consistency analysis.

4. Develop techniques and tools for analyzing the parallel activity in
systems; this includes consistency analysis, analysis of runtime behavior, and
analysis of communication errors among parallel threads of control.

5. Study the formalization of programming knowledge and its codification in
the broad spectrum languages (task 1) for use in automated knowledge-based
programming assistance.

6. Develop techniques for computer-supported reasoning as required for
advanced automated tools under tasks 1 through 5 above.

7. Design of advanced programming environments that integrate tools developed
under tasks 1 through 6 above.

C. Software Development Techniques
--------------------

Stanford will:

1. Design a high-level logic programming language using new deductive 
   techniques.

2. Develop and implement interactive and automatic systems for program 
   synthesis, program verification and planning.

3. Introduce tools for machine reasoning (automated deduction) specially
   directed toward software engineering applications

4. Investigate program manipulation techniques: maintenance, transformation, 
   and optimization.

5. Develop techniques for the verification and synthesis of concurrent 
   programs.

6. Formulate techniques for specifying, developing, and manipulating
   non-applicative programs.

7. Develop tools for rigorously establishing properties of software and 
   hardware systems (using logic of programming such as dynamic logic 
   and temporal logic).


D. DATA MANAGEMENT
------------------

Stanford will investigate advanced techniques to improve database access and
management. Within this objective we will analyze the semantics inherent in
the data and in the operations persformed on data. Where the boundaries of
algorithmic approaches are reached we will develop heuristic techniques. We 
will stress methods which are domain-independent so that the technology can
be transferred to a wide variety of applications.

Specifically we will:

1. Specify and use data semantics. We will use a categorization of data
semantics to establish those semantics which can aid in designing and
distributing well-structured databases and those which may be of operational
utility.

2. Investigate ambiguity, view and performance problems in database update.

3. Extend and develop semantic aids to the anlaysis of database contents.

4. Develop communication and audit-trail concepts in design databases.

5. Investigate algorithms for maintaining data on optical disks.

6. Acquire and maintain data resourses and database management systems to
support this research.


E. Image Understanding and Robotics
-----------------------------------
Stanford will conduct research in the area of computer vision to 
address the problems of cartography, photointerpretation and robotic sensing
as follows:

1. Analyze, design and implement intelligent systems for interpretation
and planning actions, including intelligent interfaces for users incorporating
natural language and speech I/O.

2.  Analyze and implement subsystems for geometric reasoning and reasoning in
the physical world including
representation of the physical world, problem formulation,
space/time reasoning, and general methods for using domain-specific knowledge.

3.  Investigate learning and abstraction 
in building and using databases for the physical world.

4.  Study planning, navigation and path-finding, motion control 
 map-making and world modeling for mobile robots.

5. Study the segmentation and aggregation of image features to analyze texture
    regions, canonical groupings, and figure-ground discrimination;

6. Analyze, design and implement systems for stereo mapping, motion parallax and
object motion in spatial interpretation;

7. Investigate architecture of image algorithms and their
implementation in VLSI.

8. Study mechanisms for interpretation of images including 
matching algorithms, generic models, multi-sensor integration,
geometric inference rules, and shadows.

9. Study the design of robot devices, task control, programming and planning of
actions.


F. Analysis of Algorithms
-------------------------

Stanford will perform research in creating new computer algorithms for
practical problems, develop the mathematics required to determine
efficiency of algorithms and extend programming methodology so that
such algorithms can be implemented more quickly and reliably than with
present techniques.  More specifically we will:

1. Develop new algorithms for the digital raster graphics, the
combinatorial matching problem and the "all nearest neighbors" problem.

2. Develop applications of these algorithms to a variety of problems.

3. Investigate random mappings which have applications to cryptanalysis.

4. Develop programming methodology based on the WEB programming system
which combines systems for developing programs with document formatting.


G. Relations between Algorithms and Architectures
-------------------------------------------

Stanford will investigate the relations between algorithms and computer
architectures for executing them as follows:

1. Develop algorithm-independent results on the complexity and topology
of various applications.

2. Obtain lower bounds on the optimal ratio of processor pwer to
communication capability for representative problems.

3. Relate algorithmic requirements in terms of topology, data rates,
and processor capability to physical and technological restrictions.

4. Investigate inherent tradeoffs in convergence rates and complexity
with concurrency.

5.Investigate the possibility of a metalanguage for the description
of application problems in terms of standard computational processes
which express both the complexity of the computation and its topology
and which allows accurate simulation of the process for various
architectures.